package pro.softzhang.algo.lc400;

public class LC494_TargetSum {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        public int findTargetSumWays(int[] nums, int target) {
            int sum = 0;
            for (int num : nums)
                sum += num;

            if ((sum + target) % 2 == 1 || sum < target)
                return 0;

            return subsetSum(nums, (sum + target) / 2);
        }

        private int subsetSum(int[] nums, int i) {
            int[] dp = new int[i + 1];
            dp[0] = 1;
            for (int num : nums)
                for (int j = i; j >= num; j--)
                    dp[j] += dp[j - num];
            return dp[i];
        }
    }
}
